#pragma once

namespace KTree
{
    template<class Key>
    struct BinarySerchTreeNode
    {
        typedef BinarySerchTreeNode<Key> Self;

        Self* _left;
        Self* _right;
        Key _key;

        BinarySerchTreeNode(const Key& key)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
        {}
    };

    template<class K>
    class BSTree
    {
        typedef BinarySerchTreeNode<K> Node;

    public:
        BSTree()
            :_root(nullptr)
        {}

        BSTree(const BSTree<K>& tree)
        {
            _root = _copy(tree._root);
        }

        ~BSTree()
        {
            clear();
            _root = nullptr;
        }

        void clear() { _clear(_root); }
        bool insert(const K& key);
        bool erase(const K& key);
        bool insertR(const K& key) { return _insertR(_root, key); }
        bool eraseR(const K& key) { return _eraseR(_root, key); }

        void InOrder()
        {
            _InOrder(_root);
            std::cout << std::endl;
        }

    private:
        bool _insertR(Node*& root, const K& key);
        bool _eraseR(Node*& root, const K& key);
        void _clear(Node*& root);
        Node* _copy(Node* root)
        {
            if (root == nullptr)
                return nullptr;
            
            Node* newroot = new Node(root->_key);
            newroot->_left = _copy(root->_left);
            newroot->_right = _copy(root->_right);

            return newroot;
        }

        void _InOrder(const Node* root)
        {
            if (root == nullptr)
                return;
            
            _InOrder(root->_left);
            std::cout << root->_key << " ";
            _InOrder(root->_right);
        }


    private:
        Node* _root = nullptr;
    };
}

/**
 * BStree
 * 左小右大
*/
template<class K>
bool KTree::BSTree<K>::insert(const K& key)
{
    //如果树为空直接插入
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;

    //找插入位置
    while (cur != nullptr)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else 
        {
            return false;
        }
    }

    cur = new Node(key);
    if (key < parent->_key)
        parent->_left = cur;
    else
        parent->_right = cur;
    
    return true;
}

template<class K>
bool KTree::BSTree<K>::erase(const K& key)
{
    Node* parent = nullptr;
    Node* cur = _root;

    //找要删除的节点
    while (cur != nullptr)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else//== 
        {
            Node* del = cur;
            if (cur->_left == nullptr)
            {
                if (_root == cur)
                    _root = cur->_right;
                else 
                    cur = cur->_right;
            }
            else if (cur->_right == nullptr)
            {
                if (_root == cur)
                    _root = cur->_left;
                else 
                    cur = cur->_left;
            }
            // cur == del 
            // cur有两个节点不为空
            else 
            {
                Node* minRightParent = cur;
                Node* minRight = cur->_right;

                //找右子树的最小节点
                while (minRight->_left != nullptr)
                {
                    minRightParent = minRight;
                    minRight = minRight->_left;
                }
                cur->_key = minRight->_key;

                if (minRight == minRightParent->_right)
                    minRightParent->_right = minRight->_left;
                else 
                    minRightParent->_left = minRight->_right;

                delete minRight;
                minRight = nullptr;
                return true;
            }

            if (parent->_left == del)
                parent->_left = cur;
            else if (parent->_right == del)
                parent->_right = cur;

            delete del;
            del = nullptr;
            return true;         
        }
    }

    return false;
}

template<class K>
bool KTree::BSTree<K>::_insertR(KTree::BSTree<K>::Node*& root, const K& key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        return true;
    }
    if (key < root->_key)
        return _insertR(root->_left, key);
    else if (key > root->_key)
        return _insertR(root->_right, key);
    else 
        return false;
}

template<class K>
bool KTree::BSTree<K>::_eraseR(KTree::BSTree<K>::Node*& root, const K& key)
{
    if (root == nullptr)
    {
        return false;
    }

    if (key < root->_key)
        return _eraseR(root->_left, key);
    else if (key > root->_key)
        return _eraseR(root->_right, key);
    
    // == 删除元素
    Node* del = root;
    if (root->_left == nullptr)
    {
        root = root->_right;
    }
    else if (root->_right == nullptr)
    {
        root = root->_left;
    }
    else 
    {
        Node* minRight = root->_right;
        while (minRight->_left != nullptr)
        {
            minRight = minRight->_left;
        }

        root->_key = minRight->_key;
        return _eraseR(root->_right, key);
    }

    delete del;
    return true;
}

template<class K>
void KTree::BSTree<K>::_clear(Node*& root)
{
    if (root == nullptr)
        return;
    
    _clear(root->_left);
    _clear(root->_right);
    delete root;
    root = nullptr;
}
